home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 06 - 1990 / 06.08 Aug 90 / B Trees Source / Balanced Tree / Balanced.c next >
Encoding:
C/C++ Source or Header  |  1989-12-25  |  8.6 KB  |  433 lines  |  [TEXT/nX^n]
  1. //////////////////////////////////////////////////////////////////
  2. //    
  3. //        Balanced.c
  4. //        ----------
  5. //        Balanced tree search and insertion
  6. //    
  7. //////////////////////////////////////////////////////////////////
  8.     
  9. #pragma load "managers"
  10.     
  11. //////////////////////////////////////////////////////////////////
  12. //    
  13. //        Constants and Macros
  14. //    
  15. //////////////////////////////////////////////////////////////////
  16.     
  17. #define nil                    0
  18.     
  19. //////////////////////////////////////////////////////////////////
  20. //    
  21. //        Types
  22. //    
  23. //////////////////////////////////////////////////////////////////
  24.     
  25. typedef enum {false, true} logical;
  26.  
  27. typedef struct node
  28.     {
  29.     char                *key;
  30.     struct node        *left;
  31.     struct node        *right;
  32.     int                balance;
  33.     char                *data;
  34.     } node;
  35.     
  36. //////////////////////////////////////////////////////////////////
  37. //    
  38. //        Globals
  39. //    
  40. //////////////////////////////////////////////////////////////////
  41.     
  42. //////////////////////////////////////////////////////////////////
  43. //    
  44. //        Prototypes
  45. //    
  46. //////////////////////////////////////////////////////////////////
  47.     
  48.     void initmac();
  49.     node *createnode(char *thekey, char *thedata);
  50.     unsigned int insert(node *parent, char *thekey, char *thedata);
  51.     node *lookup(node *thetable, char *thekey);
  52.     void dump(node *thetable);
  53.     void destroy(node *thetable);
  54.     
  55. //////////////////////////////////////////////////////////////////
  56. //
  57. //        main
  58. //        ----
  59. //        Test shell for lookup table package
  60. //
  61. //////////////////////////////////////////////////////////////////
  62.     
  63. main()
  64.     {
  65.     
  66.     node                *thetable;
  67.     char                thestring[256];
  68.     char                command;
  69.     char                thekey[256];
  70.     char                thedata[256];
  71.     node                *thenode;
  72.     
  73.     initmac();
  74.     
  75.     thetable = createnode("", "Data not found - empty key");
  76.     if (thetable == nil)
  77.         {
  78.         printf("\tUnable to create table\n");
  79.         exit(2);
  80.         }
  81.     
  82.     printf("? ");
  83.     while (true)
  84.         {
  85.         
  86.         gets(thestring);
  87.         sscanf(&thestring[2], "%c %s %[^\n]", &command, thekey, thedata);
  88.         
  89.         switch (command)
  90.             {
  91.             
  92.             case 'A':
  93.             case 'a':
  94.                 if (insert(thetable, thekey, thedata) == 4)
  95.                     printf("\tKey already exists in table\n");
  96.                 break;
  97.             
  98.             case 'D':
  99.             case 'd':
  100.                 dump(thetable->right);
  101.                 break;
  102.             
  103.             case 'F':
  104.             case 'f':
  105.                 thenode = lookup(thetable, thekey);
  106.                 if (thenode == nil)
  107.                     {
  108.                     printf("\tKey not found in table\n");
  109.                     break;
  110.                     }
  111.                 printf("\tData is “%s”\n", thenode->data);
  112.                 break;
  113.             
  114.             case 'Q':
  115.             case 'q':
  116.                 destroy(thetable);
  117.                 exit(0);
  118.             
  119.             }
  120.         
  121.         printf("? ");
  122.         
  123.         }
  124.     
  125.     }
  126.     
  127. //////////////////////////////////////////////////////////////////
  128. //
  129. //        initmac
  130. //        -------
  131. //        initialize any necessary managers and whatnot.
  132. //
  133. //////////////////////////////////////////////////////////////////
  134.     
  135. void initmac()
  136.     {
  137.     
  138.     InitGraf((Ptr)&qd.thePort);
  139.     SetFScaleDisable(true);
  140.     
  141.     InitCursorCtl(nil);
  142.     
  143.     }
  144.     
  145. //////////////////////////////////////////////////////////////////
  146. //
  147. //        createnode
  148. //        ----------
  149. //        create and initialize a new node
  150. //
  151. //////////////////////////////////////////////////////////////////
  152.     
  153. node *createnode(char *thekey, char *thedata)
  154.     {
  155.     
  156.     node                *thenode;
  157.     int                thelength;
  158.     
  159.     thenode = (node *)NewPtr(sizeof(node));
  160.     if (thenode == nil)
  161.         return(nil);
  162.     
  163.     thelength = 1 + strlen(thekey);
  164.     thenode->key = (char *)NewPtr(thelength);
  165.     if (thenode->key == nil)
  166.         {
  167.         DisposPtr((Ptr)thenode);
  168.         return(nil);
  169.         }
  170.     BlockMove((Ptr)thekey, (Ptr)thenode->key, thelength);
  171.     
  172.     thenode->balance = 0;
  173.     thenode->left = nil;
  174.     thenode->right = nil;
  175.     
  176.     thelength = 1 + strlen(thedata);
  177.     thenode->data = (char *)NewPtr(thelength);
  178.     if (thenode->data == nil)
  179.         {
  180.         DisposPtr((Ptr)thenode->key);
  181.         DisposPtr((Ptr)thenode);
  182.         return(nil);
  183.         }
  184.     BlockMove((Ptr)thedata, (Ptr)thenode->data, thelength);
  185.     
  186.     return(thenode);
  187.     
  188.     }
  189.     
  190. //////////////////////////////////////////////////////////////////
  191. //
  192. //        insert
  193. //        ------
  194. //        Insert a new key into the table and correct balance
  195. //        factors recursively.  The routine returns a queue of
  196. //        path directions.
  197. //
  198. //////////////////////////////////////////////////////////////////
  199.     
  200. unsigned int insert(node *parent, char *thekey, char *thedata)
  201.     {
  202.     
  203.     int                compare;
  204.     node                *high;
  205.     unsigned int    result;
  206.     node                *low;
  207.     node                *child;
  208.     
  209. //    if thekey matches this node, then return an error
  210. //        (duplicate keys)
  211.     
  212.     compare = strcmp(thekey, parent->key);
  213.     if (compare == 0)
  214.         return(4);
  215.     
  216. //    if there's a slot for the new node, then create it and return
  217. //        1 if it is to the left of parent and 2 if to the right
  218. //    else determine high, the next step in the search path
  219.     
  220.     if (compare < 0)
  221.         {
  222.         high = parent->left;
  223.         if (high == nil)
  224.             {
  225.             parent->left = createnode(thekey, thedata);
  226.             return(1);
  227.             }
  228.         }
  229.     else
  230.         {
  231.         high = parent->right;
  232.         if (high == nil)
  233.             {
  234.             parent->right = createnode(thekey, thedata);
  235.             return(2);
  236.             }
  237.         }
  238.     
  239. //    now continue the search by calling “insert” recursively
  240. //    if the result is 0 (no balancing needed at this level) or
  241. //        the result is 4 (duplicate key), return
  242.     
  243.     result = insert(high, thekey, thedata);
  244.     if ((result == 0) || (result == 4))
  245.         return(result);
  246.     
  247. //    the low 4 bits of “result” indicate the direction of the
  248. //        search path leaving “high”; increment high's balance
  249. //        if the path goes left, and decrement it if the path
  250. //        goes right
  251.     
  252.     if (result % 16 == 1)
  253.         high->balance++;
  254.     else
  255.         high->balance--;
  256.     
  257. //    if the balance is now zero, no further correction of balances
  258. //        is needed, so return
  259. //    if it's ±1, push the direction away from “parent” onto the
  260. //        “result” stack and return it
  261. //    if it's ±2, continue to balancing transformation
  262.     
  263.     switch (high->balance)
  264.         {
  265.         case 0:
  266.             return(0);
  267.         case 1:
  268.         case -1:
  269.             return((result << 4) + ((compare < 0) ? 1 : 2));
  270.         case 2:
  271.         case -2:
  272.             break;
  273.         }
  274.     
  275. //    use the direction away from “high” to find “low”, then
  276. //        switch on that direction and the next one
  277. //    the easiest way to follow these transformations is to
  278. //        refer to the pictures
  279.     
  280.     low = (result % 16 == 1) ? high->left : high->right;
  281.     switch (result % 256)
  282.         {
  283.         
  284.         case 0x11:    //    left-left case
  285.             
  286.             high->left = low->right;
  287.             low->right = high;
  288.             if (compare < 0)
  289.                 parent->left = low;
  290.             else
  291.                 parent->right = low;
  292.             high->balance = 0;
  293.             low->balance = 0;
  294.             return(0);
  295.         
  296.         case 0x12:    //    right-left case
  297.             
  298.             child = low->left;
  299.             high->right = child->left;
  300.             low->left = child->right;
  301.             if (compare < 0)
  302.                 parent->left = child;
  303.             else
  304.                 parent->right = child;
  305.             child->left = high;
  306.             child->right = low;
  307.             child->balance = 0;
  308.             low->balance = 0;
  309.             high->balance = 0;
  310.             result &= 0xF00;
  311.             if (result == 0x100)
  312.                 low->balance = -1;
  313.             else if (result == 0x200)
  314.                 high->balance = 1;
  315.             return(0);
  316.         
  317.         case 0x21:    //    left-right case
  318.             
  319.             child = low->right;
  320.             low->right = child->left;
  321.             high->left = child->right;
  322.             if (compare < 0)
  323.                 parent->left = child;
  324.             else
  325.                 parent->right = child;
  326.             child->left = low;
  327.             child->right = high;
  328.             child->balance = 0;
  329.             low->balance = 0;
  330.             high->balance = 0;
  331.             result &= 0xF00;
  332.             if (result == 0x100)
  333.                 high->balance = -1;
  334.             else if (result == 0x200)
  335.                 low->balance = 1;
  336.             return(0);
  337.         
  338.         case 0x22:    //    right-right case
  339.             
  340.             high->right = low->left;
  341.             low->left = high;
  342.             if (compare < 0)
  343.                 parent->left = low;
  344.             else
  345.                 parent->right = low;
  346.             high->balance = 0;
  347.             low->balance = 0;
  348.             return(0);
  349.         
  350.         }
  351.     
  352.     }
  353.     
  354. //////////////////////////////////////////////////////////////////
  355. //
  356. //        lookup
  357. //        ------
  358. //        Find a key in the table
  359. //
  360. //////////////////////////////////////////////////////////////////
  361.     
  362. node *lookup(node *thetable, char *thekey)
  363.     {
  364.     
  365.     node                *thenode;
  366.     int                compare;
  367.     
  368.     thenode = thetable;
  369.     
  370.     while (compare = strcmp(thekey, thenode->key))
  371.         {
  372.         if (compare < 0)
  373.             thenode = thenode->left;
  374.         else
  375.             thenode = thenode->right;
  376.         if (thenode == nil)
  377.             return(nil);
  378.         }
  379.     
  380.     return(thenode);
  381.     
  382.     }
  383.     
  384. //////////////////////////////////////////////////////////////////
  385. //
  386. //        dump
  387. //        ----
  388. //        Display the table, node by node
  389. //
  390. //////////////////////////////////////////////////////////////////
  391.     
  392. void dump(node *thetable)
  393.     {
  394.     
  395.     if (thetable == nil)
  396.         return;
  397.     
  398.     dump(thetable->left);
  399.     
  400.     printf("%10s - %2d - %10s - %10s\n",
  401.                     thetable->key, thetable->balance,
  402.                     thetable->left ? thetable->left->key : "nil",
  403.                     thetable->right ? thetable->right->key : "nil");
  404.     
  405.     dump(thetable->right);
  406.     
  407.     }
  408.     
  409. //////////////////////////////////////////////////////////////////
  410. //
  411. //        destroy
  412. //        -------
  413. //        Dispose of the table
  414. //
  415. //////////////////////////////////////////////////////////////////
  416.     
  417. void destroy(node *thetable)
  418.     {
  419.     
  420.     if (thetable == nil)
  421.         return;
  422.     
  423.     destroy(thetable->left);
  424.     destroy(thetable->right);
  425.     
  426.     DisposPtr((Ptr)thetable->key);
  427.     DisposPtr((Ptr)thetable->data);
  428.     DisposPtr((Ptr)thetable);
  429.     
  430.     }
  431.     
  432. //////////////////////////////////////////////////////////////////
  433.